#include <algorithm>  // std::sort, std::upper_bound
#include <cstdint>    // std::uint32_t
#include <iostream>   // std::cout, std::cerr
#include <sstream>    // std::istringstream
#include <stdexcept>  // std::runtime_error
#include <string>     // std::string
#include <vector>     // std::vector

/**
 * @brief 描述一个 IP 区间及其对应的城市。
 *
 * 所有区间都假定为闭区间 [start, end]，且互不重叠。
 */
struct IpRange {
    std::uint32_t start;  ///< 区间起始 IP（转换成整数）
    std::uint32_t end;    ///< 区间结束 IP（转换成整数）
    std::string city;     ///< 对应的城市名称
};

/**
 * @brief 将点分十进制 IPv4 字符串转换为 32 位无符号整数。
 *
 * 例如：把 "192.168.0.1" 转换成 0xC0A80001。
 *
 * @param ip 输入的 IPv4 字符串，格式应为 "A.B.C.D"，每段 0~255。
 * @return 转换得到的 32 位无符号整数表示。
 * @throws std::runtime_error 当字符串格式不合法时抛出异常。
 */
std::uint32_t ipv4_to_uint(const std::string& ip) {
    std::uint32_t a, b, c, d;
    char dot;  // 用于接收句点 '.'

    // 使用字符串流解析，格式形如：数字 '.' 数字 '.' 数字 '.' 数字
    std::istringstream iss(ip);
    if (!(iss >> a >> dot >> b >> dot >> c >> dot >> d)) {
        throw std::runtime_error("Invalid IPv4 string: " + ip);
    }

    // 基本校验：每段必须落在 0~255。
    if (a > 255U || b > 255U || c > 255U || d > 255U) {
        throw std::runtime_error("IPv4 octet out of range: " + ip);
    }

    // 通过位运算把四个字节拼成一个 32 位整数。
    // 注意：IPv4 按大端（network byte order）进行打包。
    return (a << 24) | (b << 16) | (c << 8) | d;
}

/**
 * @brief 根据起始 IP 对区间进行升序排序。
 *
 * 这样可以确保二分查找时，区间顺序正确。
 *
 * @param ranges 待排序的区间容器。
 */
void sort_ranges(std::vector<IpRange>& ranges) {
    std::sort(ranges.begin(), ranges.end(),
              [](const IpRange& lhs, const IpRange& rhs) {
                  return lhs.start < rhs.start;
              });
}

/**
 * @brief 利用二分查找在已排序的区间中定位指定 IP 对应的城市。
 *
 * @param ranges 已按 start 升序排列的区间列表。
 * @param ip     待查询的 IPv4（整数形式）。
 * @return 若命中区间，返回指向该区间的指针；否则返回 nullptr。
 */
const IpRange* find_city(const std::vector<IpRange>& ranges, std::uint32_t ip) {
    // upper_bound：找到第一个区间，其 start 严格大于查询 IP。
    // 这样，前一个区间（若存在）即为 start <= ip 的最后一个区间。
    auto it = std::upper_bound(ranges.begin(), ranges.end(), ip,
                               [](std::uint32_t value, const IpRange& range) {
                                   return value < range.start;
                               });

    // 如果迭代器已经在开头，说明所有区间的 start 都大于查询 IP。
    if (it == ranges.begin()) {
        return nullptr;
    }

    // 检查上一个区间是否包含该 IP。
    --it;
    if (ip <= it->end) {
        return &(*it);  // 命中：返回区间指针
    }

    // 未命中任何区间
    return nullptr;
}

int main() {
    try {
        // 1. 准备示例区间数据。
        //    实际应用中可以从配置文件、数据库或网络加载。
        std::vector<IpRange> ranges = {
            {ipv4_to_uint("1.0.0.0"),     ipv4_to_uint("1.0.0.255"),     "City A"},
            {ipv4_to_uint("2.16.0.0"),    ipv4_to_uint("2.16.255.255"),  "City B"},
            {ipv4_to_uint("10.0.0.0"),    ipv4_to_uint("10.0.0.128"),    "City C"},
            {ipv4_to_uint("123.45.67.0"), ipv4_to_uint("123.45.67.255"), "City D"}
        };

        // 2. 对区间进行排序，确保查找时有序。
        sort_ranges(ranges);

        // 3. 模拟查询：可根据需要替换为用户输入或批量查询。
        const std::vector<std::string> queries = {
            "1.0.0.42",
            "10.0.0.200",
            "123.45.67.123",
            "200.200.200.200"  // 不在任何区间内
        };

        for (const std::string& ip_str : queries) {
            // 将查询 IP 字符串转换为整数。
            std::uint32_t ip = ipv4_to_uint(ip_str);

            // 调用查找函数，判断 IP 是否落在某个区间。
            if (const IpRange* hit = find_city(ranges, ip)) {
                std::cout << ip_str << " -> " << hit->city << '\n';
            } else {
                std::cout << ip_str << " -> [未知城市]\n";
            }
        }
    } catch (const std::exception& ex) {
        // 捕获并报告异常，例如输入格式错误等。
        std::cerr << "Error: " << ex.what() << '\n';
        return 1;
    }

    return 0;
}